An essential semiconductor device is semiconductor memory, such as a random access memory (RAM) device. A RAM allows a memory circuit to execute both read and write operations on its memory cells. Typical examples of RAM devices include dynamic random access memory (DRAM) and static random access memory (SRAM).
Another form of memory is the content addressable memory (CAM) device. A conventional CAM is viewed as a static storage device constructed of modified RAM cells. A CAM is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. CAMs provide benefits over other memory search algorithms by simultaneously comparing the desired information (i.e., data in the comparand register) against the entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment, particularly routers, gateways and switches, computer systems and other devices that require rapid content searching, such as routing data or tables for data networks or matching URLs. Some of these tables are “learned” from the data passing through the network. Other tables, however, are fixed tables that are loaded into the CAM by a system controller. These fixed tables reside in the CAM for a relatively long period of time. A word in a CAM is typically large and can be 96 bits or more.
In order to perform a memory search in the above-identified manner, CAMs are organized differently than other memory devices (e.g., DRAM and SRAM). For example, an item of data is stored in a RAM in a particular location, called an address. In conventional memory devices, during a memory access, the user supplies an address and reads into (writes) or retrieves the data at the specified address. In a typical CAM, however, items of data, often referred to as “entries”, are stored in memory storage locations in a somewhat random fashion. The memory storage locations can be selected by an address bus, or an entry can be written into the first empty memory storage location. Every memory storage location has a pair of status bits that keep track of whether the memory storage location is storing valid information or is empty and available for writing.
Once an entry is stored in a CAM memory storage location, it is typically found by comparing it with data in a comparand register. When the contents stored in the CAM memory storage location do not match the data in the comparand register, the local match detection circuit returns a “no match” indication. When the contents stored in the CAM memory storage location match the data in the comparand register, the local match detection circuit returns a “match” indication.
The match and no match indications are typically provided to a priority encoder (PE) that is also part of the CAM device. If one or more local match detection circuits return a match indication, the PE also provides a “match” indication as an output. Otherwise, the PE returns a “no-match” indication. In addition, the PE identifies a memory storage location that provided a match indication and has priority, such as a highest or lowest priority, which is necessary because more than one CAM memory storage location may provide a match indication. A PE priority signal identifying a memory storage location is typically encoded as an address. Thus, with a CAM, the user supplies search data and receives an address if a match is found in memory.
Many current applications utilize ternary CAM cells, which are capable of storing three logic states. For example, the three logic states are logic “0”, logic “1”, and “don't care”. Therefore, such CAM cells require two memory cells to store the logic states, as well as a comparison circuit for comparing stored bits with search data provided to the CAM.
FIG. 1 depicts a six transistor (6T) dynamic ternary CAM memory cell 100 of the prior art. Memory cell 100 has an “x” bit and a “y” bit. For the x bit, data is written to and read out of storage capacitor Cx 140 via bit line BLx 110 and access transistor 160. For the y bit, data is written to and read out of storage capacitor Cy 142 via bit line BLy 112 and access transistor 162. The access transistors 160, 162 are controlled by a common word line 132. It should be understood that the storage capacitors can be discrete components or the parasitic capacitance of the line 132. Alternately, other storage or memory devices may be used to store data in the memory cell 100. Although not shown, other memory cells 100 in a column of a memory array are coupled either to bit line BLx 110 and bit line BLy 112 or to their complements, bit line BLx* 114 and bit line BLy* 116. Although CAM memory cell 100 is shown as a dynamic ternary CAM memory cell, the CAM memory cell may also be implemented using other types of memory storage, e.g., the CAM memory cell may use SRAM memory cells.
To store a logic “0” in memory cell 100, a “1” must be written into the x bit, and a “0” must be written into the y bit of memory cell 100. To store a logic “1” in memory cell 100, a “0” must be written into the x bit and a “1” must be written into the y bit of memory cell 100. If a “0” is stored in both the x and the y bits of memory cell 100, then memory cell 100 will be masked for a search operation because it is a “don't care”. If a “1” is stored in both the x and the y bits of memory cell 100, then memory cell 100 will always indicate a mismatch for search operations.
During a search operation, a search key/word is applied to search data lines SDx 120, SDy 122, which are coupled to the gate terminals of compare transistors 174, 176, respectively. Compare transistors 174, 176 are connected between common match line 130 and transistors 170, 172, respectively. Each transistor pair 174, 170 and 176, 172 is referred to as a compare “stack.” The applied search key is compared to data stored in memory cell 100 to see if there is a match. To search for a “0,” SDx is set to 0 and SDy is set to 1; to search for a “1,” SDx is set to 1, and SDy is set to 0. The other transistor in each compare stack is controlled by the value stored by the respective capacitors Cx 140 and Cy 142.
If both transistors of either compare stack are turned on (high in the case of NMOS transistors) then the match line 130 is pulled down indicating a mismatch. If at least one transistor on each compare stack is off (low in the case of NMOS transistors) in cell 100 and all other cells connected to match line 130, then the match line 130 remains high indicating a match.
FIG. 2 shows a CAM array 200 and associated circuits 250, 252,254, 256. The array 200 includes CAM memory cells 100 in rows and columns. Each row of CAM memory cells 100 stores an entry and is coupled to a respective word line 132 and match line 130, where every CAM memory cell 100 in the same row is mutually coupled to the word line 132 and match line 130. Each column of CAM memory cells 100 is coupled to respective search data lines SDx 120, SDy 122, and to bit lines BLx 110, BLy 112, BLx* 114, BLy* 116, where every CAM memory cell 100 in the same column is mutually coupled to the column's search data line SDx 120, SDy 122 and to either the column's bit line BLx 110 and bit line BLy 112 or the column's bit line BLx* 114 and bit line BLy* 116.
Every word line 132 is coupled to access/decode circuit 254 and to a respective word line driver 284. Every match line 130 is coupled to access/decode circuit 256 and to a respective sense amplifier 286. Every search data line SDx 120, SDy 122 is coupled to access/decode circuit 252 and to a respective search data driver 282. Every bit line BLx 110, BLy 112, BLx* 114, BLy* 116 is coupled to access/decode circuit 250, both for driving and sensing.
Testing of memory devices is extremely time consuming and costly. Testing, however, is necessary to identify errors; but conventional testing techniques, such as comparing an output address with an expected address, do not detect all defects in a CAM. If errors are not identified and repaired, stored data could become corrupted. In particular, CAM entries are often used to access addresses in networks, and data transmitted on a network may be misdirected with results ranging from nondelivery to misdelivery.
It would therefore be advantageous to have improved techniques for testing memory devices, particularly CAMs.